---
author: Marcus Rohrmoser
categories:
- de
- development
date: "2009-10-23T18:27:59+00:00"
tags:
- Binary
- Cocoa
- CoreData
- iPhone
- NSPredicate
- Objective C
- Search
title: CocoaTouch, CoreData and binary String Search
type: post
url: /2009/10/cocoatouch-coredata-and-binary-string-search/
yourls_shorturl:
- http://mro.name/3o
---
The [query optimiser][1] for [NSPredicate][2] queries ontop CoreData/SQLite on the iPhone is a bit rudimentary (cough) and so I had to optimise myself to get binary-search enabled quick results:

<!--more-->

<pre class="line-numbers"><code class="language-objc">+(NSPredicate*)findBySearchTerm:(NSString*)rawTerm within:(BOOL)within context:(NSManagedObjectContext*)context
{
    NSSet *tokens = [MovieM indexTokens:rawTerm];
    if(tokens == nil || tokens.count &lt; = 0)
        return [NSPredicate predicateWithFormat:@"FALSEPREDICATE"];
    NSMutableArray *preds = [NSMutableArray arrayWithCapacity:tokens.count];

    if(within == NO && context != nil)
    {
        // As queries aren't optimised by default we do it ourselves:
        // 1st: find matching entries from the IndexKey table - leveraging it's index:
        NSFetchRequest *fr = [[NSFetchRequest alloc] init];
        fr.entity = [NSEntityDescription entityForName:@"IndexKey" inManagedObjectContext:context];
        NSMutableSet *result = nil;
        NSError *error = nil;
        for(NSString *token in tokens)
        {
            // BETWEEN uses the table-index while BEGINSWITH does not:
            fr.predicate = [NSPredicate predicateWithFormat:@"key BETWEEN {%@, %@}", token, [MovieM upperBoundSearchString:token]];
            NSArray *keys = [context executeFetchRequest:fr error:&error];
            if(error != nil)
                NSLog(@"Oops: %@", error);
            // turn IndexKey entries to movies (join up):
            NSArray *movs = [keys valueForKey:@"movie"];
            // aggregate the results for each token:
            if(result == nil)
                result = [NSMutableSet setWithArray:movs];
            else
                [result intersectSet:[NSSet setWithArray:movs]];
        }
        [fr release];
        return [NSPredicate predicateWithFormat:@"SELF IN %@", result];
    }

    NSPredicate *template = nil;
    if(within)
        template = [NSPredicate predicateWithFormat:@"ANY index.key CONTAiNS $searchTerm"];
    else
        template = [NSPredicate predicateWithFormat:@"ANY index.key BEGINSWITH $searchTerm"];
    for(NSString *token in tokens)
    {
        NSDictionary *params = [NSDictionary dictionaryWithObject:token forKey:@"searchTerm"];
        [preds addObject:[template predicateWithSubstitutionVariables:params]];
    }
    return [NSCompoundPredicate andPredicateWithSubpredicates:preds];
}
</code></pre>

Helpers herein are

* `[MovieM indexTokens:rawTerm]` folds diacritics and uppercase and cuts at whitespace or interpunction,
* `[MovieM upperBoundSearchString:token]` which was inspired by [Apple Sample Code &#8222;DerivedProperty&#8220; `NormalizedStringTransformer::upperBoundSearchString:`][3].

 [1]: http://en.wikipedia.org/wiki/Query_optimizer
 [2]: http://developer.apple.com/iphone/library/documentation/Cocoa/Reference/Foundation/Classes/NSPredicate_Class/Reference/NSPredicate.html
 [3]: http://developer.apple.com/library/mac/#samplecode/DerivedProperty/Listings/NormalizedStringTransformer_m.html%23//apple_ref/doc/uid/DTS40007750-NormalizedStringTransformer_m-DontLinkElementID_8
